The present invention relates generally to database operations, and, more specifically, to join operations on relational database tables.
Database management systems make it possible for users to store and update large collections of information, while also supporting queries over that information. Combining data from several tables is a fundamental operation used by relational database management systems when performing database queries. In a join operation, one or more conditions specify how rows in each participating table should be related in order to generate a query result. Though the output of a join operation may be further processed to generate a query result, the cost of the join operation(s) is typically dominant in terms of both time and space. Several algorithms have been proposed for implementing joins including sort-merge join, nested-loop join, index-nested-loop join, and hash join. These algorithms are typically used to join two tables at a time, with more complex join queries broken down into a sequence of pairwise joins.